Church-Turing 论题
概述
Church-Turing 论题断言：任何直觉上"可计算"的函数都是图灵可计算的（即可被图灵机计算）。这不是数学定理，而是一个关于"计算"这一概念在自然界中本质的经验性断言，由多种计算模型的惊人等价性强力支持。
关键内容
论题的内容
Church-Turing 论题：所有可以被"有效方法"（effective method）计算的函数，都可以被图灵机计算。
"有效方法"是一个直觉性概念，指按固定规则、有限步骤、不需要创造力、机械执行的过程——就像算术运算。这个概念无法被精确数学化（一旦精确化，就已经预设了某种可计算性模型），因此论题无法被证明。
为何可信：多模型等价性
论题的经验基础是：所有被提出的"合理计算模型"都定义了同一个可计算函数类：
| 计算模型 | 提出者 | 年代 | 与图灵机的关系 |
|---|---|---|---|
| λ 演算 | 阿隆佐·邱奇</td> <td>Alonzo Church | 1936 | |
| 一般递归函数 | 库尔特·哥德尔</td> <td>Kurt Gödel / Kleene | 1936 | |
| Post 产生式系统 | Emil Post | 1943 | 等价 |
| Markov 算法 | 马尔可夫</td> <td>Andrey Markov Jr. | 1954 | |
| RAM 模型 | - | 1960s | 等价（多项式时间内） |
| 量子图灵机 | David Deutsch | 1985 | 可计算性等价 |
这种"惊人的汇聚"——完全独立发展、表面截然不同的模型，最终定义了同一个概念——是论题最有力的支撑。
论题的三个版本
| 版本 | 内容 | 地位 |
|---|---|---|
| 标准 CT 论题 | 可计算性等价 | 至今无反例，广泛接受 |
| 强 CT 论题 | 物理过程能高效模拟任意图灵机（多项式时间内） | 量子计算可能违反 |
| 物理 CT 论题 | 物理上可实现的过程都是阿兰·图灵</td> <td>图灵可计算的 |
量子计算与强论题：量子计算机在可计算性上与经典图灵机等价，但在效率上可能有指数级优势（Shor 算法）。这可能违反"强 CT 论题"，但不违反标准论题。
论题的哲学意义
- "算法"有了客观定义：不同数学家对"有效方法"的直觉，原来指向同一个数学对象
- 计算边界的确立：停机问题和所有不可判定问题，在所有合理计算模型中都不可判定
- Penrose 争议：Roger Penrose（《皇帝的新脑》）认为人类数学直觉超越图灵可计算性，但此观点存在广泛争议
与 Gödel 不完备定理的关系
两个结论共同回答了 Hilbert 纲领： - Gödel（1931）：数学有不可证的真命题（完备性的边界） - Turing/Church（1936）：有不可判定的问题（算法能力的边界）
合并解读：数学真理的范围永远超出任何形式系统，算法的能力也有根本限制——数学推理不能被完全机械化。
对 AI 研究的启示
大语言模型（如 GPT、Claude）运行在经典计算机上，受 Church-Turing 论题约束： - 无论参数规模多大，本质上都是图灵机 - 停机问题所划定的边界仍然适用 - "涌现能力"是复杂度层面的现象，不是可计算性层面的突破
来源
- raw/books/计算机科学/01-turing-on-computable-numbers.md